import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class project {
    public int maximumElementAfterDecrementingAndRearranging(int[] arr) {
        Arrays.sort(arr);
        arr[0]=1;
        for(int i=1;i<arr.length;i++){
            arr[i]=Math.min(arr[i],arr[i-1]+1);
        }
        return arr[arr.length-1];
    }

















    public int maxLevelSum(TreeNode root) {
        int max=root.val;
        int index=1;
        Queue<TreeNode> queue=new ArrayDeque<>();
        if(root!=null){
            queue.add(root);
            int layer=0;
            while (!queue.isEmpty()){
                int size=queue.size();
                int sum=0;
                layer++;
                for(int i=0;i<size;i++){
                    TreeNode tmp=queue.poll();
                    sum+=tmp.val;
                    if(tmp.left!=null){
                        queue.add(tmp.left);
                    }
                    if(tmp.right!=null){
                        queue.add(tmp.right);
                    }
                }
                if(sum>max){
                    max=sum;
                    index=layer;
                }
            }
        }
        return index;
    }


























    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
        List<TreeNode> list=new ArrayList<>();
        Set<Integer> set=new HashSet<>();
        for(int i : to_delete){
            set.add(i);
        }
        list.add(root);
        dfs(root,set,list);
        return list;
    }
    public TreeNode dfs(TreeNode root, Set<Integer> set, List<TreeNode> list){
        if(root==null){
            return null;
        }
        root.left=dfs(root.left,set,list);
        root.right=dfs(root.right,set,list);
        if(set.contains(root.val)){
            if(root.left!=null){
                list.add(root.left);
            }
            if(root.right!=null){
                list.add(root.right);
            }
            if(list.contains(root)){
                list.remove(root);
            }
            return null;
        }
        return root;
    }





















    public int scoreOfParentheses(String s) {
        Stack<Integer> stack=new Stack<>();
        int sum=0;
        char[] str=s.toCharArray();
        for(int i=0;i<str.length;i++){
            char ch=str[i];
            if(ch=='('){
                stack.push(0);
            }else{
                int up=stack.pop();
                up=up==0?1:up*2;
                if(stack.isEmpty()){
                    sum+=up;
                }else{
                    int tmp=stack.pop();
                    tmp+=up;
                    stack.push(tmp);
                }
            }
        }
        return sum;
    }
























    int count=0;
    public int pseudoPalindromicPaths (TreeNode root) {
        if(root==null){
            return 0;
        }
        dfs2(root,0);
        return count;
    }
    public void dfs2(TreeNode root,int tmp){
        tmp^=(1<<root.val);
        if(root.left==null&&root.right==null){
            if(tmp==0||((tmp&(tmp-1))==0)){
                count++;
            }
        }
        if(root.left!=null){
            dfs2(root.left,tmp);
        }
        if(root.right!=null){
            dfs2(root.right,tmp);
        }
    }
























    public int getMaximumGold(int[][] grid) {
        if(grid==null||grid.length==0){
            return 0;
        }
        int ret=0;
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                ret=Math.max(ret,dfs1(grid,i,j));
            }
        }
        return ret;
    }
    public int dfs1(int[][] arr,int row,int col){
        if(row<0||row>=arr.length||col<0||col>=arr[0].length||arr[row][col]==0){
            return 0;
        }
        int tmp=arr[row][col];
        arr[row][col]=0;
        int lower=dfs1(arr,row+1,col);
        int up=dfs1(arr,row-1,col);
        int left=dfs1(arr,row,col-1);
        int right=dfs1(arr,row,col+1);
        int max=Math.max(lower,Math.max(up,Math.max(left,right)));
        arr[row][col]=tmp;
        return tmp+max;
    }
























    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack=new Stack<>();
        int index=0;
        for(int i=0;i<pushed.length;i++){
            int tmp=pushed[i];
            stack.push(tmp);
            while (!stack.isEmpty()&&index<popped.length&&popped[index]==stack.peek()){
                stack.pop();
                index++;
            }
        }
        return index==pushed.length;
    }




















    public String modifyString(String s) {
        char[] str=s.toCharArray();
        int len=s.length();
        for(int i=0;i<len;i++){
            if(str[i]=='?'){
                for(char j='a';j<='c';j++){
                    if((i>0&&str[i-1]==j)||(i<len-1&&str[i+1]==j)){
                        continue;
                    }
                    str[i]=j;
                    break;
                }
            }
        }
        return new String(str);
    }
}
